package com.leetcode.no215;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Random;


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 小顶堆
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int num : nums) {
            pq.offer(num);
            // 堆中元素多于k个时，就删除堆顶元素 即 删除最小值
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // pq中剩下的是nums中k个最大元素
        // 堆顶是最小的，即第k个大的元素
        return pq.peek();
    }
}


//        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o2.compareTo(o1);
//            }
//        });


class Solution02 {


    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

    }

    private void shuffle(int[] nums) {
        int n = nums.length;
        Random rand = new Random();
        for (int i = 0; i < n; i++) {
            // 从 i 到最后随机选一个元素
            int r = i + rand.nextInt(n - i);
            swap(nums, i, r);
        }
    }


    private int partition(int[] nums, int left, int right) {
        if (left == right) return left;

        // 将mums[left]作为默认分界点pivot
        int pivot = nums[left];

        // j = right +1  因为会在while中先执行 --
        int i = left, j = right + 1;
        while (true) {
            // 保证nums[left,i]都小于pivot
            while (nums[++i] < pivot) {
                if (i == right) break;
            }

            // 保证nums[j,right]都大于pivot
            while (nums[--j] > pivot) {
                if (j == right) break;
            }

            if (i >= j) break;
            // 如果走到这里，一定有
            // nums[i] > pivot && nums[j] < pivot
            // 所以需要交换 nums[i] 和 nums[j]，
            // 保证 nums[left..i] < pivot < nums[j..right]
            swap(nums, i, j);
        }
        // 将pivot交换到正确位置
        swap(nums, j, left);

        // 现在 nums[left..j-1] < nums[j] < nums[j+1..right]
        return j;
    }

    public int findKthLargest(int[] nums, int k) {

        // 首先随机打乱数组
        shuffle(nums);

        int len = nums.length;
        int left = 0;
        int right = len - 1;

        // 索引转化
        k = nums.length - k;

        while (left <= right) {
            //    在nums[left,right]中选一个分界点
            int p = partition(nums, left, right);

            if (p < k) {
                // target在nums[p+1, right]中
                left = p + 1;
            } else if (p > k) {
                // target在nums[p+1, right]中
                right = p - 1;
            } else {
                // 找到第k大的元素
                return nums[p];
            }
        }
        return -1;
    }
}
